package ren.colorful.learnJava.datastructure;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

class HashTable{
	public int key = 0;		//关键字
	public int data = 0;	//数值
	public int count = 0;	//探查次数
}

public class MapDemo {
	
	private final static int MAXSIZE = 20;
	private final static int NULLKEY = 1;
	private final static int DELKEY = 2;
	private final static int SUCCESS = 0;
	private final static int FAILED = 0xFFFFFFFF;
	
	/**
	 * 创建hash表
	 * 先将hash表中各关键字清空,使其地址为开放的,然后调用插入算法将给定的关键字序列插入
	 * @param ha
	 * @param list
	 * @param p
	 * @param size
	 */
	public void createHashTable(HashTable[] ha,int[] list,int p,int size){
		int i = 0;
		//将hash表中的所有关键字清空
		for(i = 0 ; i < ha.length ; i ++){
			ha[i].key = NULLKEY;
			ha[i].count = 0;
		}
		//将关键字序列依次插入hash表中
		for(i = 0; i < list.length ; i++){
			this.insertHashTable(ha, p, size, list[i]);
		}
	}
	
	/**
	 * 将key插入hash表中,核心是hash算法
	 * @param ha
	 * @param p
	 * @param size
	 * @param key
	 */
	public void insertHashTable(HashTable[] ha,int p,int size,int key){
		int i = 1;
		int addr = 0;
		addr = key % p;//通过hash函数获取hash地址
		if(ha[addr].key == NULLKEY || ha[addr].key == DELKEY){
			ha[addr].key = key;
			ha[addr].count = 1;
		}else{
			do{
				addr = (addr + 1) % size;
				i ++;
			} while(ha[addr].key != NULLKEY && ha[addr].key != DELKEY);
			ha[addr].key = key;
			ha[addr].count = i;
		}
	}
	
	/**
	 * 查找hash表
	 * 构造hash表采用除留取余法,即 f(key) = key mode p(p <= size)
	 * 解决冲突采用开放定址法,即 f2(key) = (f(key) + i) mode p(1 <= i <= size-1)
	 * ha为hash表,p为模,size为hash表大小,key为要查找的关键字
	 */
	public int searchHashTable(HashTable[] ha,int p,int size,int key){
		int addr = key % p; //取余数
		//若发生冲突,用开放定址法赵下一个hash地址
		while(ha[addr].key != NULLKEY && ha[addr].key != key){
			addr = (addr + 1) % size;
		}
		if(ha[addr].key == key){
			return addr; 	//查找成功
		}else{	
			return FAILED;  //查找失败
		}
	}
	
	/**
	 * 删除关键字为key的记录
	 * @param ha
	 * @param p
	 * @param size
	 * @param key
	 * @return
	 */
	public int deleteHashTable(HashTable[] ha,int p,int size,int key){
		int addr = 0;
		addr = searchHashTable(ha,p,size,key);
		if(FAILED != addr){
			ha[addr].key = DELKEY;
			return SUCCESS;
		}else{
			return NULLKEY;
		}
	}
	
	/**
	 * 展示map
	 * @param ha
	 */
	public void displayHashTable(HashTable[] ha){
		int i = 0;
		System.out.format("pos: \t", "pos");
		for(i = 0; i < ha.length; i++){
			System.out.format("%s ", i);
		}
		System.out.println();
		System.out.format("key:\t");
		for(i = 0; i < ha.length; i++){
			if(ha[i].key != NULLKEY){
				System.out.format("%4d", ha[i].key);
			}else{
				System.out.format("    ");
			}
		}
		System.out.println();
		
		System.out.format("count: \t");
		for(i = 0; i < ha.length ; i++){
			if(0 != ha[i].count){
				System.out.format("%4d", ha[i].count);
			}else{
				System.out.format("    ");
			}
		}
		System.out.println();
	}
	
	public static void main(String[] args){
		int[] list = {3, 112, 245, 27, 44, 19, 76, 29, 90};
		HashTable[] ha = new HashTable[MAXSIZE];
		for(int i = 0;i < ha.length ; i ++){
			ha[i] = new HashTable();
		}
		
		MapDemo demo = new MapDemo();
		demo.createHashTable(ha, list, 19, MAXSIZE);
		demo.displayHashTable(ha);
	}
}
